package leetcode.lcp.lcp20220423;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	char R = '>';
	char L = '<';
	char U = '^';
	char D = 'v';
	char[][] matrix;
	int m, n;
	int ex, ey;
	int range;

	public int conveyorBelt(String[] matrix, int[] start, int[] end) {
		m = matrix.length;
		n = matrix[0].length();
		this.ex = end[0];
		this.ey = end[1];
		this.matrix = new char[m][];
		for (int i = 0; i < m; i++) {
			this.matrix[i] = matrix[i].toCharArray();
		}
		boolean[][] been = new boolean[m][n];
		range = Math.abs(start[0] - ex) + Math.abs(start[1] - ey) + 1;
		Integer[][][] dp = new Integer[m][n][range];
		return find(start[0], start[1], 0, been, dp);
	}

	private int find(int sx, int sy, int change, boolean[][] been, Integer[][][] dp) {
		if (sx >= m || sx < 0 || sy >= n || sy < 0 || been[sx][sy] || change >= range) {
			return Integer.MAX_VALUE;
		}
		if (sx == ex && sy == ey) {
			return change;
		}
		if (dp[sx][sy][change] != null) {
			return dp[sx][sy][change];
		}
		int ans1 = Integer.MAX_VALUE, ans2 = Integer.MAX_VALUE, ans3 = Integer.MAX_VALUE, ans4 = Integer.MAX_VALUE;
		been[sx][sy] = true;
		char direct = this.matrix[sx][sy];
		if (direct == R) {
			ans1 = this.find(sx, sy + 1, change, been, dp);
			ans2 = this.find(sx, sy - 1, change + 1, been, dp);
			ans3 = this.find(sx - 1, sy, change + 1, been, dp);
			ans4 = this.find(sx + 1, sy, change + 1, been, dp);
		} else if (direct == L) {
			ans1 = this.find(sx, sy + 1, change + 1, been, dp);
			ans2 = this.find(sx, sy - 1, change, been, dp);
			ans3 = this.find(sx - 1, sy, change + 1, been, dp);
			ans4 = this.find(sx + 1, sy, change + 1, been, dp);
		} else if (direct == U) {
			ans1 = this.find(sx, sy + 1, change + 1, been, dp);
			ans2 = this.find(sx, sy - 1, change + 1, been, dp);
			ans3 = this.find(sx - 1, sy, change, been, dp);
			ans4 = this.find(sx + 1, sy, change + 1, been, dp);
		} else {
			ans1 = this.find(sx, sy + 1, change + 1, been, dp);
			ans2 = this.find(sx, sy - 1, change + 1, been, dp);
			ans3 = this.find(sx - 1, sy, change + 1, been, dp);
			ans4 = this.find(sx + 1, sy, change, been, dp);
		}
		been[sx][sy] = false;
		int ans = Math.min(Math.min(ans1, ans2), Math.min(ans3, ans4));
		dp[sx][sy][change] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(1, this.conveyorBelt(H.str2array2("[\">>v\",\"v^<\",\"<><\"]"), H.str2array3("[0,1]"),
				H.str2array3("[2,0]")));
		H.compare(3, this.conveyorBelt(H.str2array2("[\">^^>\",\"<^v>\",\"^v^<\"]"), H.str2array3("[0,0]"),
				H.str2array3("[1,3]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
